package _021_10_6

type ListNode2 struct {
	Val  int
	Next *ListNode2
}

func Merge(pHead1 *ListNode2, pHead2 *ListNode2) *ListNode2 {
	// write code here
	newHead := new(ListNode2)
	realHead := newHead
	whoTemp := pHead2
	for pHead1 != nil && pHead2 != nil {
		if pHead1.Val < pHead2.Val {
			temp := new(ListNode2)
			temp.Val = pHead1.Val
			temp.Next = nil
			newHead.Next = temp
			pHead1 = pHead1.Next
			newHead = newHead.Next
		} else {
			temp := new(ListNode2)
			temp.Val = pHead2.Val
			temp.Next = nil
			newHead.Next = temp
			pHead2 = pHead2.Next
			newHead = newHead.Next
		}
	}
	whoTemp = pHead2
	if pHead2 == nil {
		whoTemp = pHead1
	}
	for whoTemp != nil {
		temp := new(ListNode2)
		temp.Val = whoTemp.Val
		temp.Next = nil
		newHead.Next = temp
		newHead = newHead.Next
		whoTemp = whoTemp.Next
	}
	return realHead.Next
}
